#include "llist.h"

/* Initialize a new singly linked list */
list_t *make_empty_list(void)
{
  list_t *list;
 
  /*allocate space*/
  list = (list_t*) safe_malloc( sizeof(list_t) );

  /*initialize list*/
  list->head = NULL;
  list->foot = NULL;
  list->list_len = 0;  
   
  return list; 
}

/* Free a list and all satellite data */
void free_list(list_t *list, void (*destroy_fptr)(void *))
{
  int i;
  lnode_t *current, *tmp;
  
  if( list == NULL || destroy_fptr == NULL )
    return;

  current = list->head;
  
  /*if the list is empty then just free list pointer*/
  if( list->head == NULL  || list->foot == NULL )
  {
     free(list);
  }

  for(i=0; i<(list->list_len); i++)
  {
    tmp = current;
    current = current->next;
    destroy_fptr(tmp); 
  } 
 
  free(list);
       
}


/* Insert a new item at the end of the current list */
list_t *insert_at_foot(list_t *list, void *value)
{
  lnode_t *tmp;
   
  if( list == NULL || value == NULL )
    return NULL;

  /*create a new node*/
  tmp = (lnode_t*)safe_malloc( sizeof(lnode_t) );
  tmp->next = NULL;
  tmp->data = value;

  /*if it's an empty list*/
  if( list->head == NULL )
  {
    list->head = list->foot = tmp;
    list->list_len++;    
    return list;
  }

   
  list->foot->next = tmp;
  list->foot = tmp; 
  list->list_len++;

  return list;
}

  

/* Insert a new item into the list ordered according to the cmp function 
 * pointer constraints .*/
list_t *insert_in_order(list_t *list, void *value, 
                        int (*cmp_fptr)(const void *, const void *) )
{
  lnode_t *last, *current, *tmp;

  if ( list == NULL || value == NULL || cmp_fptr == NULL )
    return NULL;

  tmp = (lnode_t*)safe_malloc( sizeof(lnode_t) );
  tmp->data = value;

  /*if list is empty*/
  if ( list->head == NULL )
  {
    list->head = list->foot = tmp;
    list->list_len++;      
  }

  /*test if the value bigger than the last item of the list*/
  if ( cmp_fptr(value, list->foot->data) >= 0)
  {
     return insert_at_foot(list, value);
  }

   
  current = list->head;
  last = NULL;
  while( current != NULL && cmp_fptr(value, current->data) >= 0 )
  {
    last = current;
    current = current->next; 
  } 
 
  /*value is less than value of the first item*/
  if( last == NULL )
  {
    tmp->next = list->head;
    list->head = tmp;
    list->list_len++;      
    return list;
  }


  list->list_len++;      
  tmp->next = last->next;
  last->next = tmp;
  return list;   
 
}

/*fine an elmenet by its id*/
void *find_element_by_id(list_t *list, size_t id)
{
   lnode_t *current;
   
   if(list == NULL)
    return NULL;
   
   current = list->head;
   id--;

   while(current != NULL && id >0)
   {
     current = current->next;
     id--; 
   }   
  
   if( id != 0 )
   {
     fprintf(stderr, "List error !\n");
     exit(-1);
   } 
   return current->data; 
}

/* Find an item in the list, return NULL if not found */
void *find_element(list_t *list, void *value,
                   int (*cmp_fptr)(const void *, const void *))
{
   
  lnode_t *current;
  size_t *id = (size_t*)safe_malloc(sizeof(size_t));
 
   
  if( list == NULL || value == NULL || cmp_fptr == NULL )
    return NULL;

  if( list->head == NULL )
    return NULL;

  *id = 0;
  current = list->head;
  while( cmp_fptr(value, current->data) && current->next != NULL )
  {
     current = current->next;
     (*id)++;
  } 

  if( !cmp_fptr(value, current->data) )
    return id;
  
  return NULL;

}


/*copy node */
lnode_t *copy_node(lnode_t *item)
{
  lnode_t *tmp;
  if( item == NULL )
    return NULL;

  tmp = safe_malloc(sizeof(lnode_t));
  tmp->next = item->next;
  tmp->data = item->data;
  return tmp;
}


/*delete node*/
void delete_node(list_t *list, lnode_t *item)
{
  lnode_t *current, *last;

  if( list == NULL || item == NULL )
    return;

  current = list->head;
  last = NULL;

  while( current != NULL && current != item )
  {
    last = current;
    current = current->next;
  }
  
  if( current != NULL && current == item )  
  {
     last->next = current->next;
     free(current); 
  }
}


/* Insertion sort for link list items using a user defined cmp function */
list_t *sort_list (list_t *list,
                   int (*cmp_fptr)(const void *, const void *) )
{
  
  lnode_t *current,  *tmp, *last;
  int i, len; /*len is the length of sorted sublist*/

  if( list == NULL || cmp_fptr == NULL )
    return NULL;

  /*if list is an empty list or just has one node ,return list*/
  if( list->head == NULL || list->head->next == NULL )
    return list;

  len = 0;
  last = NULL;
  current = list->head;
  tmp = copy_node(list->head->next);
  delete_node(list, list->head->next);

  while( len <= (list->list_len) && tmp != NULL )
  {
     i = 0;   

     while( i <= len && cmp_fptr(tmp->data, current->data) >= 0 ) 
     {
       last = current;
       current = current->next; 
       i++;
     } 
  
     tmp->next = current;  
     if(last != NULL )
        last->next = tmp; 
     else
        list->head = tmp;
    
     /*init for next loop*/
     len++;

     /*init tmp , tmp is the next elemenet of sorted sublist*/
     tmp = list->head;
     for(i=0; i <= len; i++)
     {
       tmp = tmp->next; 
     } 
     last = copy_node(tmp);
     delete_node(list, tmp);
     tmp = last;

     last = NULL;
     current = list->head;

  } 
 
  current = list->head;
  while( current->next )
  {
    current = current->next; 
  }

  list->foot = current; 
  return list; 

}


/* Print all the elements in the list */
void printList(list_t *list, void (*print)(const void*) )
{
  lnode_t *current;

  if( list == NULL )
    return;

  if( list->head == NULL )
  {
    printf("List is empty!\n");
    return; 
  }

  current = list->head;
  while( current )
  {
    print( current->data );
    current = current->next;
  }

}

/* traverse the list and generate dict */
void generate_dict(FILE *dict, list_t *list)
{
  lnode_t *current;
  char *st;
  size_t len, i; /*length of words or non-words*/
   
  if( dict == NULL || list == NULL )
    return;  
 
  current = list->head;
  while( current != NULL )
  {
     st = (char*)current->data; 
     len = strlen(st);
     fprintf(dict, "%d", len);
     for(i=0; i<len; i++)
     {
       fprintf(dict, " %d", st[i]);
     }  
     fprintf(dict, "\n");
    
     current = current->next;
  } 

}
